A conventional database system uses a datastore to persistently store data pages, and a cache to provide fast access to the data pages. For example, in response to a request to access a data page, the data page is loaded from the datastore into the cache, and may thereafter be accessed from and/or modified within the cache. Once the data stored in the cache reaches a maximum allowed size, data pages are deallocated from the cache according to a replacement policy. For example, a replacement policy may result in deallocation of the oldest data pages in the cache until the data stored in the cache is of an acceptable size.
A modern in-memory database system uses volatile memory (e.g., Random Access Memory) for its cache and for persistent storage. Accordingly, it may be advantageous to selectively increase or decrease the cache size based on competing needs of the database system. A replacement policy is also required in order to deallocate cached data pages so that the maximum cache size may be decreased to a desired level.
Many types of replacement policies exist. A least-recently used (LRU) policy may, for example, maintain a linked list of all cached data pages. The list is ordered based on the time at which each page was last used. For example, the least-recently used page is located at the end of the list, while the most-recently used page is located at the beginning of the list. If a command is received to free a particular amount of cache space, a number of data pages having a total size equal to or greater than the particular amount is identified from the end of the list and deallocated.
A conventional LRU policy therefore requires modification of the linked list in response to every page usage. Modification of the list requires an exclusive lock and therefore contention for the lock and resulting inefficiencies would be significant.